package leetcode.templates.sorts;

import java.util.Arrays;

import leetcode.helper.HelpDebug;

/**
 * 基数排序
 *
 * @author CaoYu
 * @date 2022年3月21日
 * @description
 */
public class MaxRadixSort {

	public static int[] sort(int[] nums) {
		int max = Integer.MIN_VALUE;
		for (int num : nums) {
			max = Math.max(max, num);
		}
		int base = 1;
		int len = nums.length;
		int[] buf = new int[len];
		while (base <= max) {
			int[] bucket = new int[10];
			for (int num : nums) {
				int idx = num / base % 10;
				bucket[idx] += 1;
			}
			int sum = 0;
			for (int i = 9; i >= 0; i--) {
				sum += bucket[i];
				bucket[i] = len - sum;
			}
			for (int num : nums) {
				int idx = num / base % 10;
				buf[bucket[idx]] = num;
				bucket[idx]++;
			}
			nums = Arrays.copyOf(buf, len);
			base *= 10;
		}
		return nums;
	}

	public static void main(String[] args) {
		int[] ans = MaxRadixSort.sort(HelpDebug.str2array3("[4,0,10,5]"));
		HelpDebug.print(ans);
	}
}
